Že pri prejšnjih nalogah smo spoznali SSČS. Ponovimo še enkrat - seznam seznamov celih števil (SSCŠ) je seznam, katerega elementi so bodisi cela števila bodisi seznami seznamov celih števil. Da bo enostavneje, recimo, da je tudi prazen seznam SSCŠ. Nekaj primerov:
[-1, 2, -3]
[1, [2], 3, [2, 3, 4]]
[[[[0]], 1], [2, [[-3], [4]]]]Sestavi funkcijo ločiStevila(sscs), ki vrne trojico (poz, nic, neg), ki pove
koliko je v sscs pozitivnih, ničelnih in koliko negativnih celih števil. Za primere od zgoraj so rezultati:
(1, 0, 2)
(6, 0, 0)
(3, 1, 1)Predpostavi, da je parameter zagotovo SSCS,
def ločiStevila(sscs): '''Razdeli podatke v SSCS na pozitivne, ničelne in negativne''' if len(sscs) == 0 : # tudi prazen seznam je SSCS return (0, 0, 0) # in nima celih števil kolikoPozStevil = 0 kolikoNegStevil = 0 kolikoNic = 0 # pregledamo vse elemente for el in sscs : # če je element 'običajno število' if isinstance(el, int): if el > 0: kolikoPozStevil += 1 elif el < 0: kolikoNegStevil += 1 else: kolikoNic += 1 else : # potem mora pa biti sscs in moramo prešteti vsa cela števila v njem trojka = ločiStevila(el) kolikoPozStevil, kolikoNic, kolikoNegStevil = kolikoPozStevil + trojka[0], \ kolikoNic + trojka[1], kolikoNegStevil + trojka[2] return kolikoPozStevil, kolikoNic, kolikoNegStevil
Sestavi funkcijo jeSSCS(sscs), ki preveri
(vrne True oz. False), če je dan seznam res seznam seznamov celih števil.
POZOR: Python pravi, da je isinstance(True, int) enako True, pa tudi
isinstance(False, int) enako True, zato se "znebi" napačnih logičnih
vrednosti z isinstance(True, bool)
def jeSSCS(sscs): '''Ali je sscs res seznam seznamov celih števil''' if not isinstance(sscs, list): # če sploh ne gre za seznam return False if len(sscs) == 0 : # tudi prazen seznam je SSCS return True # pregledamo vse elemente for el in sscs : # če je element logična vrednost if isinstance(el, bool): return False # če element ni ne SSCS ne celo število if not isinstance(el, int) and \ not jeSSCS(el) : # ne SSCE return False # vsi testi OK return True
Sestavi funkcijo kolikoNapacnih(sscs), ki prešteje,
koliko je v seznamu seznamov celih števil napačnih podatkov, torej elementov, ki
niso ne cela števila, ne SSCŠ. Če argument ni seznam, vrni None
>>>kolikoNapacnih([1, 'bla', 2])
1
>>>kolikoNapacnih([1, [['bla', 'blu'], False], 2])
1
>>>kolikoNapacnih([[1.8], [2, 3, [4]], [False, 4, [True]]])
2
>>>kolikoNapacnih(12)
Nonedef kolikoNapacnih(sscs): '''Koliko elementov je v sscs napačnih''' if not isinstance(sscs, list): return None kolikoNarobe = 0 # pregledamo vse elemente for el in sscs: if (not isinstance(el, int)) and (not jeSSCS(el)) \ or isinstance(el, bool): kolikoNarobe += 1 return kolikoNarobe
Oznake idej se nanašajo na prosojnice permutacije v spletni učilnici FMF za predmet Programiranje 1 v š.l. 15/16
Če hočemo narediti permutacijo iz 0 elementov, vrnemo tako kot itertools [[]]
Na osnovi ideje 1 smo zgradili osnutek metode permutacijeV1(seznam).
Dopolni ga do delujočega!
def permutacijeV1(seznam):
'''Vrne seznam seznamov, kjer posamezni seznam predstavlja
permutacijo elementov iz seznama '''
... manjka
prviDel = seznam[:-1]
zadnji = seznam[-1]
permPrej = permutacijeV1(prviDel)
# vstavi zadnji na vsa možna mesta
rez = []
for
koncnaPer = permPrej z vstavljenim zadnjim
rez.append(koncnaPer)
...
return sorted(rez)def permutacijeV1(seznam): '''Vrne seznam seznamov, kjer posamezni seznam predstavlj permutacijo elementov iz seznama ''' if seznam == []: # ni elementov, le prazna permutacija return [[]] if len(seznam) == 1: # en sam element - ena permutacija! return [[seznam[0]]] prviDel = seznam[:-1] zadnji = seznam[-1] permPrej = permutacijeV1(prviDel) rez = [] for posameznaP in permPrej: '''Iz te perm. naredimo len(seznam) novih ''' for i in range(len(seznam)): novaP = posameznaP[:] novaP.insert(i, zadnji) rez.append(novaP) return sorted(rez)
Na osnovi ideje 2 smo zgradili osnutek metode permutacijeV2(seznam).
Dopolni ga do delujočega!
def permutacijeV2(seznam):
'''Vrne seznam seznamov, kjer posamezni seznam predstavlja
permutacijo elementov iz seznama '''
... manjka
vse = []
for ind, elt in enumerate(seznam):
# zgradimo vse permutacije iz ostalih
vsePerm = permutacijeV2(seznam[:ind] + seznam[ind + 1:] )
# in sedaj permutacijam dodamo na začetek element elt
...
...
return sorted(vse)def permutacijeV2(seznam): '''Vrne seznam seznamov, kjer posamezni seznam predstavlja permutacijo elementov iz seznama ''' if seznam == []: # ni elementov, le prazna permutacija return [[]] vse = [] for ind, elt in enumerate(seznam): # zgradimo vse permutacije iz ostalih vsePerm = permutacijeV2(seznam[:ind] + seznam[ind + 1:] ) # in sedaj permutacijam dodamo na začetek element elt for perm in vsePerm: vse.append([elt] + perm) return sorted(vse)
Na osnovi ideje 3 smo zgradili osnutek metode permutacijeV3(seznam).
Dopolni ga do delujočega!
def permutacijeV3(seznam, doSedaj = []):
'''Vrne seznam vseh možnih permutacij iz elementov v elementi,
ki imajo začetek enak permutaciji, ki so predstava doSedaj'''
# Če smo že na koncu
return [doSedaj]
vse = []
for elt in seznam:
# če elt še lahko dodamo v doslej sestavljeno permutacijo
# generiramo vse permutacije z začetkom doSedaj + [elt]
# dodamo vsem
return sorted(vse)def permutacijeV3(seznam, doSedaj = []): '''Vrne seznam vseh možnih permutacij iz elementov v elementi, ki imajo začetek enak permutaciji, ki so predstava doSedaj''' if seznam == []: # ni elementov, le prazna permutacija return [[]] if len(seznam) == len(doSedaj):# Če smo že na koncu return [doSedaj] vse = [] for elt in seznam: if not elt in doSedaj: # če elt še lahko dodamo v doslej sestavljeno permutacijo permut = permutacijeV3(seznam, doSedaj + [elt]) # generiramo vse permutacije z začetkom doSedaj + [elt] vse += permut #dodamo vsem return sorted(vse)
Na osnovi ideje 4 smo zgradili osnutek metode permutacijeV4(seznam).
Dopolni ga do delujočega!
import itertools
def permutacijeV4(seznam):
'''Vrne seznam seznamov, kjer posamezni seznam predstavlja
permutacijo elementov iz seznama '''
# uporabimo itertools
# pazimo, ker ta vrne seznam naborov!
return sorted(vse)import itertools def permutacijeV4(seznam): '''Vrne seznam seznamov, kjer posamezni seznam predstavlja permutacijo elementov iz seznama ''' # uporabimo itertools permu = itertools.permutations(seznam) vse = list(map(list, permu)) # pazimo, ker ta vrne seznam naborov! return sorted(vse)
Sestavi funkcijo izbrisiPrazneMape(potDoMape),
ki v izbrani mapi (in njenih podmapah) pobriše vse prazne datoteke
(tiste z velikostjo 0) in vse prazne mape (tiste, ki ne vsebujejo nobenih datotek ali podmap).
Funkcija naj vrne par, ki ga sestavljata število pobrisanih datotek in število pobrisanih map,
oziroma None, če potDoMape ne opisuje imenika
Pozor: ko zbrišemo prazno datoteko, se lahko sprazni tudi mapa.
Pred testiranjem vedno skopirajte to
datoteko ZIP
(staro mapo PythonOsRek pobrišite!)
in jo razširite (nastala bo mapa PythonOsRek s podmapami testX in EURO2012)
import os def izbrisiPrazneMape(potDoMape): '''Izbriši vse prazne datoteke in prazne mape''' kolikoDat, kolikoMap = 0, 0 if not os.path.isdir(potDoMape): # ni mapa return None vseDat = os.listdir(potDoMape) for datoteka in vseDat: #izbrisemo samo prazne datoteke if os.path.isfile(potDoMape + "\\" + datoteka) and os.path.getsize(potDoMape + "\\" + datoteka) == 0: os.remove(potDoMape + "\\" + datoteka) kolikoDat += 1 elif os.path.isdir(potDoMape + "\\" + datoteka): #filtriramo mape kolDat, kolMap = izbrisiPrazneMape(potDoMape + "\\" + datoteka) kolikoDat += kolDat kolikoMap += kolMap #če je mapa sedaj prazna, jo izbrisemo if len(os.listdir(potDoMape)) == 0: os.rmdir(potDoMape) kolikoMap += 1 return kolikoDat, kolikoMap
Collatzovo zaporedje tvorimo na sledeč način. Začnemo z nekim naravnim
številom
Vse naloge, razen prve, rešite z rekurzijo!
Sestavite funkcijo naslednji_clen(n), ki izračuna člen, ki v Collatzovemu
zaporedju sledi številu n.
def naslednji_clen(n): '''člen, ki v Collatzovemu zaporedju sledi številu `n`''' if n % 2 == 0: return n // 2 else: return 3 * n + 1
Sestavite funkcijo dolzina_zaporedja(n), ki izračuna dolžino Collatzovega
zaporedja, ki se začne s številom n.
def dolzina_zaporedja(n): '''dolžina Collatzovega zaporedja, ki se začne s številom `n`.''' if n == 1: return 1 else: return 1 + dolzina_zaporedja(naslednji_clen(n))
Sestavite funkcijo najvecji_clen(n), ki izračuna največji člen v
Collatzovem zaporedju, ki se začne s številom n.
def najvecji_clen(n): '''največji člen v Collatzovem zaporedju, ki se začne s številom `n`.''' if n == 1: return 1 else: return max(n, najvecji_clen(naslednji_clen(n)))
Sestavite funkcijo najdaljse_zaporedje(m, n), ki vrne dolžino najdaljšega
zaporedja med vsemi tistimi Collatzovimi zaporedji, ki se začnejo s števili
med (vključno) m in n.
def najdaljse_zaporedje(m, n): '''Dolžina najdaljšega zaporedja med vsemi tistimi Collatzovimi zaporedji, ki se začnejo s števili med (vključno) m in n.''' if m == n: return dolzina_zaporedja(m) else: return max(dolzina_zaporedja(m), najdaljse_zaporedje(m + 1, n))